Mùa đông năm 1944, Văn Cao gặp Vũ Quý, một cán bộ Việt Minh, ở ga Hàng Cỏ. Vũ Quý là người từng quen biết Văn Cao và đã động viên ông viết những bài hát yêu nước như Đống Đa, Thăng Long hành khúc ca... Vũ Quý đề nghị Văn Cao thoát ly hoạt động cách mạng, và nhiệm vụ đầu tiên là sáng tác một bài hành khúc cho đội quân Việt Minh.[2]

Văn Cao viết bài hát đó trong nhiều ngày tại căn gác số 45 Nguyễn Thượng Hiền. Ông có viết lại trong một ghi chép tháng 7 năm 1976 như sau: "...Tôi chỉ đang làm một bài hát. Tôi chưa được biết chiến khu, chỉ biết những con đường Phố Ga, đường Hàng Bông, đường Bờ Hồ theo thói quen tôi đi. Tôi chưa gặp các chiến sĩ cách mạng của chúng ta, trong khóa quân chính đầu tiên ấy, và biết họ hát như thế nào. Ở đây đang nghĩ cách viết một bài hát thật giản dị cho họ có thể hát được...".[2] Trong một hồi ký tựa đề "Bài Tiến quân ca",[3] Văn Cao cho biết, khi ông sáng tác Tiến quân ca thì có Ph. D ở cùng, và "Anh rất tôn trọng những phút tôi ngồi vào bàn với tập bản thảo và chờ đợi âm thanh từng câu nhạc được nhắc đi nhắc lại. Anh là người chứng kiến sự ra đời của bài Tiến quân ca".[3][4]

Về ca khúc, Văn Cao nói rằng, tên bài hát và lời ca của nó là một sự tiếp tục từ ca khúc Thăng Long hành khúc ca trước đó: "Cùng tiến bước về phương Thăng Long thành cao đứng" và bài Đống Đa: "Tiến quân hành khúc ca, thét vang rừng núi xa"... Và ông đã rút lại những ca từ trong bài hát đó thành Tiến quân ca.[2] Phần ca từ trong bài hát ở thời điểm mới ra đời có nhiều khác biệt so với sau này,[5][6] như câu đầu Đoàn quân Việt Nam đi, thì ban đầu là Đoàn quân Việt Minh đi,[5] câu thứ sáu của bài hát ở phiên bản đầu là "Thề phanh thây uống máu quân thù"[6][7] thể hiện sự căm phẫn, đau đớn của Văn Cao trước sự tàn bạo của thực dân Pháp và trước nạn đói đang xảy ra, về sau được nhiều người góp ý, tác giả đã sửa thành Đường vinh quang xây xác quân thù.[5] Câu kết: "Tiến lên! Cùng thét lên! Chí trai là nơi đây ước nguyền!" được Văn Cao sửa thành (...) Núi sông Việt Nam ta vững bền, nhưng đến khi xuất bản thành Quốc ca, ai đó đã sửa thành (...) Nước non Việt Nam ta vững bền, việc này, theo Văn Cao, "Với một ca khúc đòi hỏi trang nghiêm, chữ nước non hát lên bị yếu. Chữ núi sông hát khỏe và hùng tráng".[5]

Sau khi hoàn thành tác phẩm, Văn Cao gặp và hát cho Vũ Quý nghe. Vũ Quý rất hài lòng, giao cho Văn Cao tự tay viết bài hát lên đá in. Và lần đầu tiên Tiến quân ca được in trên trang văn nghệ của báo Độc Lập tháng 11 năm 1944 bằng bản in đá do chính Văn Cao viết.

Ngày 17 tháng 8 năm 1945, ca khúc được hát trước quần chúng lần đầu tiên tại một cuộc mít-tinh của công chức Hà Nội bởi Ph. D, đây cũng là người đã buông lá cờ đỏ sao vàng của Việt Minh thay cho cờ của chính phủ Trần Trọng Kim và cướp loa phóng thanh hát Tiến quân ca, mà theo Văn Cao: "Con người trầm lặng ấy đã có sức hát hấp dẫn hàng vạn quần chúng ngày hôm đó".[3][4]

Còn nhà thơ, nhạc sĩ Nguyễn Đình Thi, sau khi nghe Văn Cao hát bài hát này, đã xúc động thật sự, và đề nghị mỗi người viết một bài hát nữa về mặt trận Việt Minh. Sau đó Nguyễn Đình Thi viết được bài Diệt phát xít, Văn Cao viết thêm bài Chiến sĩ Việt Nam, cả hai bài hát này đều phổ biến rộng rãi trong công chúng.